package main
/**
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树[1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3


但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3


进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
 */

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	//从两个子节点开始判断
	return isSymmetricHelper(root.Left, root.Right)
}
func isSymmetricHelper(left ,right *TreeNode) bool  {
	//如果左右子节点都为空，说明当前节点是叶子节点，返回true
	if left ==nil && right == nil {
		return true
	}
	//如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
	if left==nil || right == nil || left.Val!=right.Val {
		return false
	}
	//然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
	return isSymmetricHelper(left.Left,right.Right) && isSymmetricHelper(left.Right,right.Left)
}
func main() {

}
